//Two Sum 

/*

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <time.h>
#include <math.h>
#include <algorithm>
#include <iostream>
using namespace std;

void print(vector<int>&ivec){
	for(vector<int>::iterator it=ivec.begin();it!=ivec.end();it++){
		cout<<*it<<" ";
	}
	cout<<endl;
}
void print2(int *index,int n){
	for(int i=0;i<n;i++)
		cout<<index[i]<<" ";
	cout<<endl;
}

int partition(vector<int> &nums,int *index,int low,int high){
	srand((int)time(0));
	int h=low+rand()%(high-low+1);
	swap(nums[low],nums[h]);
	swap(index[low],index[h]);
	int x=nums[low],index_x=index[low]; 
	int i=low,j=high;
	while(i<j){
		while(i<j&&nums[j]>x)
			j--;
		nums[i]=nums[j];
		index[i]=index[j];
		while(i<j&&nums[i]<=x)
			i++;
		nums[j]=nums[i];
		index[j]=index[i];
	}
	nums[i]=x;
	index[i]=index_x;
	return i;
}

void quickSort(vector<int>& nums,int * index,int left,int right){
	if(left<right){
		int pos=partition(nums,index,left,right);
		quickSort(nums,index,left,pos-1);
		quickSort(nums,index,pos+1,right);
	}
}

void swap(int &a,int &b){
	int c=a;
	a=b;
	b=c;
}
vector<vector<int>> threeSum(vector<int>& nums){
	int a,b,c,tmp=0;
	int n=nums.size();
	vector<vector<int>> ans;
	vector<int> m;
	if(n<3)
		return ans;
	sort(nums.begin(),nums.end());
	//print(nums);
	for(int i=0;i<nums.size()-2;i++){
		if(nums[i]>0)
			break;
		for(int k=i+1;k<nums.size()-1;k++){
			if(nums[k]+nums[i]>0)
				break;
			for(int w=k+1;w<nums.size();w++){
				if(nums[k]+nums[i]+nums[w]>0)
					break;
				if(nums[k]+nums[i]+nums[w]==0){
					m.push_back(nums[i]);
					m.push_back(nums[k]);
					m.push_back(nums[w]);
					ans.push_back(m);
					m.clear();
				}
			}

		}
	}
	return ans;
}
vector<int> twoSum(vector<int>& nums, int target){
	int *index=(int *)malloc(sizeof(int)*nums.size());
	for(int i=0;i<nums.size();i++)
		index[i]=i;
	quickSort(nums,index,0,nums.size()-1);
	vector<int>ans(2,-1);
	for(int a=0,b=nums.size()-1;a!=b;){
		if(nums[a]+nums[b]==target){
			ans[0]=index[a]>index[b]?index[b]+1:index[a]+1;
			ans[1]=index[a]>index[b]?index[a]+1:index[b]+1;
			break;
		}
		else if(nums[b]>target-nums[a])
			b--;
		else if(nums[a]<target-nums[b])
			a++;
	}
	return ans;
}
int main(){
	int numbers[]={16,-6,-9,2,7,11,15},numbers2[3];
	vector< int > ivec( numbers2, numbers2 );
	vector<vector<int>> ans;
	 
	ans=threeSum(ivec);
	//print(ans);

	system("pause");
	return 0;
}

*/